﻿// demostu5.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <stdlib.h>

using namespace std;

typedef struct _LinkNode
{
	int data; // 数据域
	struct _LinkNode* next; // 指针域
}LinkNode, LinkList;

// 链表 的头部 LinkList
bool InitList(LinkList*& L)
{
	L = new LinkNode; // 分配新的节点

	// 如果分配内存失败，就退出程序
	if (!L)
	{
		return false;
	}
	L->next = NULL; // 把指针域置为 空
	L->data = -1; // 数据域初始值为 -1
	return true;
}

//前插入数据         
bool InitInsert_front(LinkList*& L, LinkNode* node)
{
	
	if (!L || !node)
	{
		return false;
	}
	node->next = L->next;//新节点node的next指向L->next也就是NULL
	L->next = node;//L->next指向node
	return true;
}

//后插入数据 
bool InitInsert_back(LinkList*& L, LinkNode* node)
{
	LinkList* last = NULL;
	if (!L || !node) 
	{
		return false;
	} 
	
	last = L;
	
	while (last->next)
	{
		last = last->next;  //last就指向last->next内存
	}

	node->next = NULL;//node->next内存指向NULL
	last->next = node;//last->next指向node
	return true;
}

// 指定位置 插入数据
bool InitInsert(LinkList*& L, int i, int& e)
{
	if (!L)
	{
		return false; 
	}
	int j = 0;
	LinkList* p, * s;
	p = L;

	while (p && j < i - 1)
	{
		p = p->next;
		j++;
	}

	if (!p || j > i - 1)
	{
		return false;
	}

	s = new LinkNode;
	s->data = e;
	s->next = p->next;
	p->next = s;

	return true;
}

//指定位置获取元素
bool Link_GetElem(LinkList*& L, int i, int& e)
{
	int j;
	LinkList* p;

	if (!L || !L->next)
	{
		return false;
	}
	p = L->next;
	j = 1;

	while (j < i && p)
	{
		p = p->next;
		j++;
	}

	if (!p || j > i)
	{
		return false;
	}

	e = p->data;
	return true;
}

//指定元素获取位置
bool Link_FindElem(LinkList*& L, int e, int& index)
{
	LinkList* p;
	p = L->next;
	index = 1;
	if (!L || !L->next)
	{
		index = 0;
		return false;
	}

	while (p && p->data != e)
	{
		p = p->next;
		index++;
	}

	if (!p)
	{
		index = 0;
		return false;
	}

	return true;
}

//删除元素
bool LinkDelete(LinkList*& L, int i)
{
	LinkList* p, * q;

	int index = 0;
	p = L;

	if (!L || !L->next)
	{
		return false;
	}

	while ((p->next) && (index < i - 1))
	{
		p = p->next;
		index++;
	}

	if (!p->next || (index > i - 1))
	{
		return false;
	}

	q = p->next;
	p->next = q->next;
	delete q;
	return true;
}

//销毁链表
void LinkListDestroy(LinkList*& L)
{
	LinkList* p = L;
	cout << "销毁链表" << endl;

	while (p)
	{
		L = L->next;
		delete p;
		p = L;
	}
}

//遍历链表
void ListPrint(LinkList*& L)
{
	LinkNode* p = NULL;
	if (!L)
	{
		cout << "链表为空" << endl;
		return;
	}

	p = L->next; // 过滤掉 -1

	int i = 0;
	while (p)
	{
		cout << p << ": " << p->data << "\t";
		p = p->next;
	}
	cout << endl;
}

int main(void)
{
	LinkList* L = NULL;
	LinkNode* s = NULL;

	cout << "初始化链表" << endl;

	if (InitList(L))
	{
		cout << "初始化成功" << endl;
	}

	cout << "(前)请输入数据的次数:";
	int n = 0;
	cin >> n;
	while (n > 0)
	{
		cout << "前插入请输入元素 :" << endl;
		s = new LinkNode;
		cin >> s->data;
		InitInsert_front(L, s);
		n--;
	}
	ListPrint(L);

	cout << "(后)请输入数据的次数:";
	int c = 0;
	cin >> c;
	while (c > 0)
	{
		cout << "后插入请输入元素 :" << endl;
		s = new LinkNode;
		cin >> s->data;
		InitInsert_back(L, s);
		c--;
	}
	ListPrint(L);

	// 任意位置插入元素 
	for (int j = 0; j < 3; j++)
	{
		int i, x;
		cout << "请输入插入的位置和元素（用空格隔开）:";
		cin >> i;
		cin >> x;
		if (InitInsert(L, i, x))
		{
			cout << "插入成功.\n\n";
		}
		else
		{
			cout << "插入失败!\n\n";
		}
		ListPrint(L);
	}

	// 单链表根据位置获取元素 
	int element = 0;
	if (Link_GetElem(L, 2, element))
	{
		cout << "获取第二个元素成功, 值：" << element << endl;
	}
	else
	{
		cout << "获取第二个元素失败!" << endl;
	}

	// 单链表根据值查询元素所在的位置 
	int index = 0;
	if (Link_FindElem(L, 10, index))
	{
		cout << "查找元素 10 存在,所在位置: " << index << endl;
	}
	else
	{
		cout << "不存在元素 10." << endl;
	}

	// 单链表删除元素 
	if (LinkDelete(L, 2))
	{
		cout << "删除第 2 个元素成功!" << endl;
		ListPrint(L);
	}
	else
	{
		cout << "删除第 2 个元素失败!" << endl;
	}

	//9. 销毁单链表
	LinkListDestroy(L);
	system("pause");
	return 0;
}


// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
